package h0723;

import java.util.*;
/**
  * @description 建立哈夫曼树
  * @author 不知名帅哥
  * @date 2024/7/23 14:00
  * @version 1.0
*/
public class HuffmanTree {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=sc.nextInt();
        }
        getResult(arr);
    }

    private static void getResult(int[] arr) {
        PriorityQueue<Node> tree=new PriorityQueue<>((o1, o2) -> {
            if (o1.weight!= o2.weight){
                return o1.weight- o2.weight;
            }else {
                return o1.height-o2.height;
            }
        });

        //构建树
        for (int i : arr) {
            Node node=new Node(null,null,i,0);
            tree.offer(node);
        }

        while (tree.size()>1){
            Node lc = tree.poll();
            Node rc = tree.poll();

            Node newNode=new Node(lc,rc,lc.weight+rc.weight,rc.height+1);
            tree.offer(newNode);
        }
        //poll出最后一个节点，即根节点
        Node root = tree.poll();
        List<Integer> list=new ArrayList<>();
        inOrder(root,list); //中序遍历输出
        StringJoiner joiner=new StringJoiner(" ");
        for (Integer i : list) {
            joiner.add(i+"");
        }
        System.out.println(joiner);
    }

    //中序遍历二叉树
    private static void inOrder(Node root, List<Integer> list) {
        if (root==null){
            return;
        }
        inOrder(root.lchild,list);
        list.add(root.weight);
        inOrder(root.rchild,list);
    }

    static class Node{
        Node lchild;
        Node rchild;
        int weight; //当前节点权重
        int height; //当前节点代表子树的高度

        public Node(Node lc,Node rc,int weight,int height){
            this.lchild=lc;
            this.rchild=rc;
            this.weight=weight;
            this.height=height;
        }
    }

}
